package leetcode.graph;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author wangmaolin1
 * @date 2023/11/12 23:59
 */
public class _210 {
    private boolean hasCycle;
    private boolean[] visited;
    private boolean[] path;
    private List<Integer> postOrder;

    /**
     * 现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [ai, bi] ，表示在选修课程 ai 前
     * 必须 先选修 bi 。
     * <p>
     * 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。
     * 返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。
     * <p>
     * 就是求图的拓扑排序 -> 无环 && return 后序遍历的逆序
     * 1.构建图
     * 2.判断是否有环
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<Integer>[] gragh = buildGraph(numCourses, prerequisites);
        visited=new boolean[numCourses];
        path=new boolean[numCourses];
        postOrder=new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            track(gragh, i);
        }
        if (hasCycle) {
            return new int[]{};
        }
        int[]res=new int[numCourses];
        Collections.reverse(postOrder);
        /*int lastIndex = postOrder.size() - 1;
        for (int i = lastIndex; i >=0; i--) {
            res[i]=postOrder.get(i);
        }*/
        for (int i = 0; i < postOrder.size(); i++) {
            res[i] = postOrder.get(i);
        }
        return res;
    }

    private void track(List<Integer>[] gragh, int i) {

        if (path[i]) {
            hasCycle = true;
        }
        if (visited[i] || hasCycle) {
            return;
        }
        visited[i] = true;
        path[i] = true;
        for (Integer integer : gragh[i]) {
            track(gragh, integer);
        }
        postOrder.add(i);
        path[i] = false;
    }

    private List<Integer>[] buildGraph(int numCourses, int[][] prerequisites) {
        List<Integer>[] gragh = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            gragh[i] = new ArrayList<>();
        }
        for (int[] prerequisite : prerequisites) {
            gragh[prerequisite[1]].add(prerequisite[0]);
        }
        return gragh;
    }
}
